package p2;

// Murat Muratovic
// CS 4500 03/23/2012
// P1

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Vector;


public class P2Graph {

	protected Vector<P2Nodes> nodes = new Vector<P2Nodes>();
	protected Vector<Edge> edges = new Vector<Edge>();
	protected boolean directed = false;
	protected boolean sortedNeighbors = false;

	public double[][] getAdjacencyMatrix() {
		double[][] adjMatrix = new double[nodes.size()][nodes.size()];

		for (int i = 0; i < nodes.size(); i++)
			for (int j = 0; j < nodes.size(); j++)
				if (i == j)
					adjMatrix[i][j] = 0;
				else
					adjMatrix[i][j] = Double.POSITIVE_INFINITY;

		for (int i = 0; i < nodes.size(); i++) {
			P2Nodes node = nodes.elementAt(i);

			for (int j = 0; j < edges.size(); j++) {
				Edge edge = edges.elementAt(j);

				if (edge.a == node) {
					int indexOfNeighbor = nodes.indexOf(edge.b);

					adjMatrix[i][indexOfNeighbor] = edge.weight;
				}
			}
		}

		return adjMatrix;
	}

	public void setDirected() {
		directed = true;
	}

	public void setUndirected() {
		directed = false;
	}

	public boolean isDirected() {
		return directed;
	}

	public boolean isSortedNeighbors() {
		return sortedNeighbors;
	}

	public void setSortedNeighbors(boolean flag) {
		sortedNeighbors = flag;
	}

	public int indexOf(P2Nodes a) {
		for (int i = 0; i < nodes.size(); i++)
			if (nodes.elementAt(i).data.equals(a.data))
				return i;

		return -1;
	}

	public Vector<P2Nodes> getNodes() {
		return nodes;
	}

	public Vector<Edge> getEdges() {
		return edges;
	}

	public P2Nodes getNodeAt(int i) {
		return nodes.elementAt(i);
	}

	public void unvisitAllNodes() {
		for (int i = 0; i < nodes.size(); i++)
			nodes.elementAt(i).unvisit();
	}

	public Vector<P2Nodes> getNeighbors(P2Nodes a) {
		Vector<P2Nodes> neighbors = new Vector<P2Nodes>();

		for (int i = 0; i < edges.size(); i++) {
			Edge edge = edges.elementAt(i);

			if (edge.a == a)
				neighbors.add(edge.b);

			if (!directed && edge.b == a)
				neighbors.add(edge.a);
		}

		if (sortedNeighbors)
			Collections.sort(neighbors);

		return neighbors;
	}

	public int addNode(P2Nodes a) {
		nodes.add(a);

		return nodes.size() - 1;
	}

	public void addEdge(Edge a) {
		edges.add(a);

		if (!directed)
			edges.add(new Edge(a.b, a.a, a.weight));
	}

	public void printNodes() {
		System.out.println(nodes);
	}

	public void printEdges() {
		System.out.println(edges);
	}

}

class P2SecondGraph {
	// symbol table of linked lists
	private LinkListSymbols st; 
	
	// a graph with no vertices or edges
	public P2SecondGraph() {
		st = new LinkListSymbols();
	}

	// add v to w's list of neighbors and w to v's list of neighbors
	// parallel edges allowed
	public void addEdge(String v, String w) {
		if (st.get(v) == null)
			addVertex(v);
		if (st.get(w) == null)
			addVertex(w);
		LinkListAdjacency vlist = (LinkListAdjacency) st.get(v);
		LinkListAdjacency wlist = (LinkListAdjacency) st.get(w);
		vlist.insert(w);
		wlist.insert(v);
	}

	// add a new vertex v with no neighbors
	public void addVertex(String v) {
		st.put(v, new LinkListAdjacency());
	}

	// return the degree of vertex v
	public int degree(String v) {
		LinkListAdjacency adjlist = (LinkListAdjacency) st.get(v);
		if (adjlist == null)
			return 0;
		else
			return adjlist.size();
	}

	// return the array of vertices incident to v
	public String[] neighbors(String v) {
		LinkListAdjacency adjlist = (LinkListAdjacency) st.get(v);
		if (adjlist == null)
			return new String[0];
		else
			return adjlist.toArray();
	}

	// not very efficient,intended for debugging only
	public String toString() {
		String s = "";
		String[] vertices = st.keys();
		for (int v = 0; v < vertices.length; v++) {
			LinkListAdjacency adjlist = (LinkListAdjacency) st.get(vertices[v]);
			s += vertices[v] + ": " + adjlist + "\n";
		}
		return s;
	}
}

class LinkListAdjacency {
	private Node first; // beginning of list
	private int N; // size of list

	// helper linked list data type
	private static class Node {
		String name;
		Node next;

		Node(String name, Node next) {
			this.name = name;
			this.next = next;
		}
	}

	public boolean isEmpty() {
		return (first == null);
	}

	public int size() {
		return N;
	}

	// add s to the adjacency list
	public void insert(String s) {
		first = new Node(s, first);
		N++;
	}

	// return string representation of list 
	// (in reverse order of list)
	public String toString() {
		String s = "";
		for (Node x = first; x != null; x = x.next)
			s = x.name + ", " + s;
		return "{ " + s + "}";
	}

	// return array of strings comprising this adjacency list
	public String[] toArray() {
		String[] names = new String[N];
		int i = N;
		for (Node x = first; x != null; x = x.next)
			names[--i] = x.name;
		return names;
	}


}

class Routes {
	private HashSet visited = new HashSet(); // vertices on the stack
	private LinkedList path = new LinkedList(); 
	// the path - use a Stack instead
	private P2SecondGraph G;
	private String s, t;
	static ArrayList<List<String>> paths;

	public Routes(P2SecondGraph G, String s, String t) {
		this.G = G;
		this.s = s;
		this.t = t;
	}

	// show all simple paths from s to t
	public int count() {
		return 0;
	}

	// show all simple paths from s to t - use DFS
	public ArrayList<List<String>> show() {
		paths = new ArrayList<List<String>>();
		show(s);
		return paths;
	}

	// use DFS
	private void show(String v) {

		// add node s to current path
		path.addLast(v);

		// found path from s to t
		if (v.equals(t)) {
			paths.add(new ArrayList<String>(path));
		}

		// consider all neighbors that would
		// continue path with repeating a node
		else {
			String[] neighbors = G.neighbors(v);
			for (int i = 0; i < neighbors.length; i++) {
				String w = neighbors[i];
				if (!path.contains(w))
					show(w);
			}
		}

		// done exploring from v
		// remove from path
		path.removeLast();
	}
}

class LinkListSymbols {
	private HashMap st = new HashMap();

	public void put(String key, Object value) {
		st.put(key, value);
	}

	public Object get(String key) {
		return st.get(key);
	}

	public String toString() {
		return st.toString();
	}

	public String[] keys() {
		Set keyvalues = st.entrySet();
		String[] keys = new String[st.size()];
		Iterator it = keyvalues.iterator();
		for (int i = 0; i < st.size(); i++) {
			Map.Entry entry = (Map.Entry) it.next();
			keys[i] = (String) entry.getKey();
		}
		return keys;
	}
}
